package skiplist

import "math/rand"

const (
	SKIPLIST_P = 0.5
	MAX_LEVEL  = 16
)

type Node struct {
	key      string
	data     interface{}
	forwards []*Node // 每一层：该node 所指向的下一个节点
}

func NewNode(key string, data interface{}, level int) *Node {
	return &Node{
		key:      key,
		data:     data,
		forwards: make([]*Node, level),
	}
}

type SkipList struct {
	header *Node
	length int
	level  int
}

func NewSkipList(opt ...int) *SkipList {
	return &SkipList{
		header: &Node{forwards: make([]*Node, MAX_LEVEL)},
	}
}

func randomLevel() int {
	level := 1
	for rand.Float32() < SKIPLIST_P && level < MAX_LEVEL {
		level++
	}

	return level
}

// Front returns first element in the skiplist which maybe nil.
func (skl *SkipList) Front() *Node {
	return skl.header.forwards[0]
}

// Next returns first element after e.
func (n *Node) Next() *Node {
	if n != nil {
		return n.forwards[0]
	}

	return nil
}

func (s *SkipList) Search(key string) (*Node, bool) {
	x := s.header
	for curLevel := s.level - 1; curLevel >= 0; curLevel-- {
		for x.forwards[curLevel] != nil && x.forwards[curLevel].key < key {
			x = x.forwards[curLevel]
		}
	}

	x = x.forwards[0]
	if x != nil && x.key == key {
		return x, true
	}

	return nil, false
}

func (s *SkipList) Insert(key string, data interface{}) *Node {
	// update 记录要每一层要更新的node
	update := make([]*Node, MAX_LEVEL)
	x := s.header

	for i := s.level - 1; i >= 0; i-- {
		for x.forwards[i] != nil && x.forwards[i].key < key {
			x = x.forwards[i]
		}

		update[i] = x
	}

	x = x.forwards[0]

	// 找到节点，直接更新
	if x != nil && x.key == key {
		x.data = data
		return x
	}

	level := randomLevel()
	if level > s.level {
		level = s.level + 1
		// 意思是header 的下一个节点要指向新的node
		update[s.level] = s.header
		s.level = level
	}

	node := NewNode(key, data, level)
	for i := 0; i < level; i++ {
		node.forwards[i] = update[i].forwards[i]
		update[i].forwards[i] = node
	}

	s.length++
	return node
}

func (s *SkipList) Del(key string) *Node {
	update := make([]*Node, MAX_LEVEL)
	x := s.header
	for i := s.level - 1; i >= 0; i-- {
		for x.forwards[i] != nil && x.forwards[i].key < key {
			x = x.forwards[i]
		}
		update[i] = x
	}
	x = x.forwards[0]

	if x != nil && x.key == key {
		for i := 0; i < s.level; i++ {
			if update[i].forwards[i] != x {
				return nil
			}
			update[i].forwards[i] = x.forwards[i]
		}
		s.length--
	}
	return x

}
